home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre4.z / postgre4 / src / planner / prep / prepqual.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-08-27  |  16.5 KB  |  669 lines
  1.  
  2. /*     
  3.  *      FILE
  4.  *         prepqual
  5.  *     
  6.  *      DESCRIPTION
  7.  *         Routines for preprocessing the parse tree qualification
  8.  *     
  9.  */
  10. /* RcsId ("$Header: /private/postgres/src/planner/prep/RCS/prepqual.c,v 1.22 1992/08/03 23:49:49 joey Exp $");  */
  11.  
  12. /*     
  13.  *      EXPORTS
  14.  *             preprocess-qualification
  15.  */
  16.  
  17. #include "nodes/pg_lisp.h"
  18.  
  19. #include "planner/clauses.h"
  20. #include "planner/internal.h"
  21. #include "planner/clause.h"
  22. #include "planner/clauses.h"
  23. #include "planner/prepqual.h"
  24. #include "utils/lsyscache.h"
  25.  
  26. /*    
  27.  *        preprocess-qualification
  28.  *    
  29.  *        Driver routine for modifying the parse tree qualification.
  30.  *    
  31.  *        Returns the new base qualification and the existential qualification
  32.  *        in a list.
  33.  *    
  34.  */
  35.  
  36. /*  .. init-query-planner    */
  37.  
  38. LispValue
  39. preprocess_qualification (qual,tlist)
  40.      LispValue qual,tlist ;
  41. {
  42.     LispValue cnf_qual = cnfify (qual, true);
  43.     LispValue existential_qual =
  44.       update_clauses (lispCons (lispInteger((int)_query_result_relation_),
  45.                 update_relations (tlist)),
  46.               cnf_qual,(LispValue)_query_command_type_);
  47.     if ( existential_qual ) 
  48.       return (lispCons (set_difference (cnf_qual,existential_qual),
  49.             lispCons(existential_qual,LispNil)));
  50.     else 
  51.       return (lispCons (cnf_qual,lispCons(existential_qual,LispNil)));
  52.     
  53. }  /* function end   */
  54.  
  55. /*         =======================
  56.  *         CNF CONVERSION ROUTINES
  57.  *         =======================
  58.  */
  59.  
  60. /*     
  61.  *      NOTES:
  62.  *         The basic algorithms for normalizing the qualification are taken
  63.  *         from ingres/source/qrymod/norml.c
  64.  *     
  65.  *         Remember that the initial qualification may consist of ARBITRARY
  66.  *         combinations of clauses.  In addition, before this routine is called,
  67.  *         the qualification will contain explicit "AND"s.
  68.  *     
  69.  */
  70.  
  71. /*    
  72.  *        cnfify
  73.  *    
  74.  *        Convert a qualification to conjunctive normal form by applying
  75.  *        successive normalizations.
  76.  *    
  77.  *        Returns the modified qualification with an extra level of nesting.
  78.  *
  79.  *      If 'removeAndFlag' is true then it removes the explicit ANDs.
  80.  *
  81.  *    NOTE: this routine is called by the planner (removeAndFlag = true)
  82.  *    and from the rule manager (removeAndFlag = false).
  83.  *    
  84.  */
  85.  
  86. /*  .. preprocess-qualification, print_parse    */
  87.  
  88. LispValue
  89. cnfify (qual, removeAndFlag)
  90.      LispValue qual ;
  91.      bool removeAndFlag;
  92. {
  93.     LispValue newqual = LispNil;
  94.  
  95.     if ( consp (qual) ) {
  96.     newqual = find_nots (pull_args (qual));
  97.     newqual = normalize (pull_args (newqual));
  98.     newqual = qualcleanup (pull_args (newqual));
  99.     newqual = pull_args (newqual);;
  100.     
  101.     if (removeAndFlag) {
  102.         if(and_clause (newqual)) 
  103.           newqual=remove_ands(newqual);
  104.         else 
  105.           newqual=remove_ands(make_andclause(lispCons(newqual,LispNil)));
  106.     }
  107.     }
  108.     else if ( !lispNullp(qual) )
  109.     newqual = lispCons(qual, LispNil);
  110.  
  111.     return (newqual);
  112.  
  113. } /*  function end   */
  114.  
  115. /*    
  116.  *        pull-args
  117.  *    
  118.  *        Given a qualification, eliminate nested 'and' and 'or' clauses.
  119.  *    
  120.  *        Returns the modified qualification.
  121.  *    
  122.  */
  123.  
  124. /*  .. cnfify, pull-args    */
  125.  
  126. LispValue
  127. pull_args (qual)
  128.      LispValue qual ;
  129. {
  130.   if(null (qual)) 
  131.     return (LispNil);
  132.   else 
  133.     if (is_clause (qual)) 
  134.       return(make_clause (get_op (qual),
  135.          lispCons(pull_args ((LispValue)get_leftop (qual)),
  136.              lispCons(pull_args ((LispValue)get_rightop(qual)),
  137.                   LispNil))));
  138.  
  139.     else 
  140.       if (and_clause (qual)) {
  141.     LispValue temp = LispNil;
  142.     LispValue t_list = LispNil;
  143.  
  144.     foreach (temp,get_andclauseargs(qual)) 
  145.       t_list = nappend1 (t_list, pull_args(CAR(temp)));
  146.     return (make_andclause (pull_ands (t_list)));
  147.       }
  148.       else 
  149.     if (or_clause (qual)) {
  150.       LispValue temp = LispNil;
  151.       LispValue t_list = LispNil;
  152.       
  153.       foreach (temp,get_orclauseargs(qual)) 
  154.         t_list = nappend1 (t_list, pull_args(CAR(temp)));
  155.       return (make_orclause (pull_ors (t_list)));
  156.     }
  157.     else 
  158.       if (not_clause (qual)) 
  159.         return (make_notclause (pull_args (get_notclausearg (qual))));
  160.       else 
  161.         return (qual);
  162. } /* function end  */
  163.  
  164. /*    
  165.  *        pull-ors
  166.  *    
  167.  *        Pull the arguments of an 'or' clause nested within another 'or'
  168.  *        clause up into the argument list of the parent.
  169.  *    
  170.  *        Returns the modified list.
  171.  */
  172.  
  173. /*  .. distribute-args, pull-args, pull-ors   */
  174.  
  175. LispValue
  176. pull_ors (orlist)
  177.      LispValue orlist ;
  178. {
  179.   if(null (orlist)) 
  180.     return (LispNil);
  181.   else 
  182.     if (or_clause (CAR (orlist))) 
  183.       return (pull_ors (nconc(CopyObject(get_orclauseargs(CAR(orlist))),
  184.                  CopyObject(CDR (orlist)))));
  185.     else 
  186.       return (lispCons (CAR (orlist),pull_ors (CDR (orlist))));
  187. }  /* function end   */
  188.  
  189. /*    
  190.  *        pull-ands
  191.  *    
  192.  *        Pull the arguments of an 'and' clause nested within another 'and'
  193.  *        clause up into the argument list of the parent.
  194.  *    
  195.  *        Returns the modified list.
  196.  */
  197.  
  198. /*  .. pull-ands, pull-args    */
  199.  
  200. LispValue
  201. pull_ands (andlist)
  202.      LispValue andlist ;
  203. {
  204.   if(null (andlist)) 
  205.     return (LispNil);
  206.   else 
  207.     if (and_clause (CAR (andlist))) 
  208.       return (pull_ands(nconc(CopyObject(get_andclauseargs(CAR(andlist))),
  209.                  CopyObject(CDR (andlist)))));
  210.     else 
  211.       return (lispCons (CAR (andlist),pull_ands (CDR (andlist))));
  212. }  /* function end   */
  213.  
  214. /*    
  215.  *        find-nots
  216.  *    
  217.  *        Traverse the qualification, looking for 'not's to take care of.
  218.  *        For 'not' clauses, remove the 'not' and push it down to the clauses'
  219.  *        descendants.
  220.  *        For all other clause types, simply recurse.
  221.  *    
  222.  *        Returns the modified qualification.
  223.  *    
  224.  */
  225.  
  226. /*  .. cnfify, find-nots, push-nots    */
  227.  
  228. LispValue
  229. find_nots (qual)
  230.      LispValue qual ;
  231. {
  232.   if(null (qual)) 
  233.     return (LispNil);
  234.   else 
  235.     if (is_clause (qual)) 
  236.       return (make_clause (get_op (qual),
  237.           lispCons(find_nots ((LispValue)get_leftop (qual)),
  238.               lispCons( find_nots ((LispValue)get_rightop (qual)),
  239.                 LispNil))));
  240.     else 
  241.       if (and_clause (qual)) {
  242.     LispValue temp = LispNil;
  243.     LispValue t_list = LispNil;
  244.  
  245.     foreach (temp,(get_andclauseargs(qual))) {
  246.       t_list = nappend1(t_list,find_nots(CAR(temp)));
  247.     }
  248.  
  249.     return (make_andclause (t_list));
  250.       } else
  251.     if (or_clause (qual)) {
  252.       LispValue temp = LispNil;
  253.       LispValue t_list = LispNil;
  254.  
  255.       foreach (temp,get_orclauseargs(qual)) {
  256.         t_list = nappend1(t_list,find_nots(CAR(temp)));
  257.       }
  258.       return (make_orclause (t_list));
  259.     } else
  260.       if (not_clause (qual)) 
  261.         return (push_nots (get_notclausearg (qual)));
  262.       else 
  263.         return (qual);
  264. } /* function end   */
  265.  
  266. /*    
  267.  *        push-nots
  268.  *    
  269.  *        Negate the descendants of a 'not' clause.
  270.  *    
  271.  *        Returns the modified qualification.
  272.  *    
  273.  */
  274.  
  275. /*  .. find-nots, push-nots    */
  276.  
  277. LispValue
  278. push_nots (qual)
  279.      LispValue qual ;
  280. {
  281.     if(null (qual)) 
  282.     return (LispNil);
  283.   else 
  284.     /*    Negate an operator clause if possible: */
  285.     /*       ("NOT" (< A B)) => (> A B) */
  286.     /*    Otherwise, retain the clause as it is (the 'not' can't be pushed */
  287.     /*    down any farther). */
  288.  
  289.     if(is_clause (qual)) {
  290.     LispValue oper = get_op (qual);
  291.     ObjectId negator = get_negator (get_opno ((Oper)oper));
  292.     if(negator) 
  293.     {
  294.       Oper op = (Oper) MakeOper (negator,
  295.                      InvalidObjectId,
  296.                      get_oprelationlevel ((Oper)oper),
  297.                      get_opresulttype ((Oper)oper), NULL, NULL);
  298.       op->op_fcache = (FunctionCache *) NULL;
  299.       return (lispCons((LispValue)op, lispCons((LispValue)get_leftop (qual),
  300.                     lispCons((LispValue)get_rightop (qual),
  301.                          LispNil))));
  302.     }
  303.     else 
  304.       return (make_notclause (qual));
  305.     }
  306.     else 
  307.       /*    Apply DeMorgan's Laws: */
  308.       /*       ("NOT" ("AND" A B)) => ("OR" ("NOT" A) ("NOT" B)) */
  309.       /*       ("NOT" ("OR" A B)) => ("AND" ("NOT" A) ("NOT" B)) */
  310.       /*    i.e., continue negating down through the clause's descendants. */
  311.       if (and_clause (qual)) {
  312.     LispValue temp = LispNil;
  313.     LispValue t_list = LispNil;
  314.  
  315.     foreach(temp,get_andclauseargs(qual)) {
  316.       t_list = nappend1(t_list,push_nots(CAR(temp)));
  317.     }
  318.     return (make_orclause (t_list));
  319.       }
  320.       else 
  321.     if (or_clause (qual)) {
  322.       LispValue temp = LispNil;
  323.       LispValue t_list = LispNil;
  324.  
  325.       foreach(temp,get_orclauseargs(qual)) {
  326.         t_list = nappend1(t_list,push_nots(CAR(temp)));
  327.     }
  328.     return (make_andclause (t_list));
  329.     }
  330.     else 
  331.       /*    Another 'not' cancels this 'not', so eliminate the 'not' and */
  332.       /*    stop negating this branch. */
  333.       if (not_clause (qual)) 
  334.         return (find_nots (get_notclausearg (qual)));
  335.       else  
  336.         /*    We don't know how to negate anything else, */
  337.         /*      place a 'not' at this */
  338.         /*    level. */
  339.         return (make_notclause (qual));
  340.  
  341. }  /* function end  */
  342.  
  343. /*    
  344.  *        normalize
  345.  *    
  346.  *        Given a qualification tree with the 'not's pushed down, convert it
  347.  *        to a tree in CNF by repeatedly applying the rule:
  348.  *            ("OR" A ("AND" B C))  => ("AND" ("OR" A B) ("OR" A C))
  349.  *        bottom-up.
  350.  *        Note that 'or' clauses will always be turned into 'and' clauses.
  351.  *    
  352.  *        Returns the modified qualification.
  353.  *    
  354.  */
  355.  
  356. /*  .. cnfify, normalize
  357.  */
  358. LispValue
  359. normalize (qual)
  360.      LispValue qual ;
  361. {
  362.   if(null (qual)) 
  363.     return (LispNil);
  364.   else 
  365.     if (is_clause (qual)) 
  366.       return (make_clause (get_op (qual),
  367.           lispCons(normalize ((LispValue)get_leftop (qual)),
  368.               lispCons( normalize ((LispValue)get_rightop (qual)),
  369.                 LispNil))));
  370.     else 
  371.       if (and_clause (qual)) {
  372.     LispValue temp = LispNil;
  373.     LispValue t_list = LispNil;
  374.  
  375.     foreach (temp,get_andclauseargs(qual)) {
  376.       t_list = nappend1(t_list,normalize(CAR(temp)));
  377.     }
  378.     return (make_andclause (t_list));
  379.       } else
  380.     if (or_clause (qual)) {
  381.       /* XXX - let form, maybe incorrect */
  382.       LispValue orlist = LispNil;
  383.       LispValue temp = LispNil;
  384.       LispValue has_andclause = LispNil;
  385.  
  386.       foreach(temp,get_orclauseargs(qual)) {
  387.         orlist = nappend1(orlist,normalize(CAR(temp)));
  388.       }
  389.       temp = LispNil;
  390.       /*  XXX was some  */
  391.       foreach (temp,orlist) {
  392.         if ( and_clause (CAR(temp)) )
  393.           has_andclause = LispTrue;
  394.         if (has_andclause == LispTrue)
  395.           break;
  396.       }
  397.       if(has_andclause == LispTrue) 
  398.         return (make_andclause (or_normalize (orlist)));
  399.       else 
  400.         return (make_orclause (orlist));
  401.  
  402.     } else
  403.       if (not_clause (qual)) 
  404.         return (make_notclause (normalize (get_notclausearg (qual))));
  405.       else 
  406.         return (qual);
  407.  
  408. }  /* function end   */
  409.  
  410. /*    
  411.  *        or-normalize
  412.  *    
  413.  *        Given a list of exprs which are 'or'ed together, distribute any
  414.  *        'and' clauses.
  415.  *    
  416.  *        Returns the modified list.
  417.  *    
  418.  */
  419.  
  420. /*  .. distribute-args, normalize, or-normalize    */
  421.  
  422. LispValue
  423. or_normalize (orlist)
  424.      LispValue orlist ;
  425. {
  426.      if ( consp (orlist) ) {
  427.       LispValue distributable = LispNil;
  428.       LispValue new_orlist = LispNil;
  429.       LispValue temp = LispNil;
  430.       
  431.       foreach(temp,orlist) {
  432.            if (and_clause(CAR(temp)) )
  433.          distributable = CAR(temp);
  434.       }
  435.       if (distributable)
  436.         new_orlist = LispRemove(distributable,orlist);
  437.       
  438.       if(new_orlist) 
  439.         return (or_normalize (lispCons (distribute_args 
  440.                     (CAR (new_orlist),
  441.                      get_andclauseargs (distributable)),
  442.                     CDR (new_orlist))));
  443.       
  444.       else
  445.         return (orlist);
  446.       
  447.      }
  448.      return(NULL);
  449. }  /* function end   */
  450.  
  451. /*    
  452.  *        distribute-args
  453.  *    
  454.  *        Create new 'or' clauses by or'ing 'item' with each element of 'args'.
  455.  *        E.g.: (distribute-args A ("AND" B C)) => ("AND" ("OR" A B) ("OR" A C))
  456.  *    
  457.  *        Returns an 'and' clause.
  458.  *    
  459.  */
  460.  
  461. /*  .. or-normalize     */
  462.  
  463. LispValue
  464. distribute_args (item,args)
  465.      LispValue item,args ;
  466. {
  467.     LispValue or_list = LispNil;
  468.     LispValue n_list = LispNil;
  469.     LispValue temp = LispNil;
  470.     LispValue t_list = LispNil;
  471.  
  472.     if(null (args))
  473.       return (item);
  474.  
  475.     foreach (temp,args) {
  476.     n_list = or_normalize(pull_ors(lispCons(item,
  477.                         lispCons(CAR(temp),LispNil))));
  478.     or_list = make_orclause(n_list);
  479.     t_list = nappend1(t_list,or_list);
  480.     }
  481.     return (make_andclause (t_list));
  482.  
  483. }  /* function end  */
  484.  
  485. /*    
  486.  *        qualcleanup
  487.  *    
  488.  *        Fix up a qualification by removing duplicate entries (left over from
  489.  *        normalization), and by removing 'and' and 'or' clauses which have only
  490.  *        one valid expr (e.g., ("AND" A) => A).
  491.  *    
  492.  *        Returns the modified qualfication.
  493.  *    
  494.  */
  495.  
  496. /*  .. qualcleanup, cnfify    */
  497.  
  498. LispValue
  499. qualcleanup (qual)
  500.      LispValue qual ;
  501. {
  502.      if(null (qual)) 
  503.        return (LispNil);
  504.      else 
  505.        if (is_clause (qual)) 
  506.      return (make_clause (get_op (qual),
  507.              lispCons(qualcleanup ((LispValue)get_leftop (qual)),
  508.              lispCons( qualcleanup((LispValue)get_rightop(qual)),
  509.                    LispNil))));
  510.        else 
  511.      if (and_clause (qual)) {
  512.           LispValue temp = LispNil;
  513.           LispValue t_list = LispNil;
  514.           LispValue new_and_args = LispNil;
  515.  
  516.           foreach(temp,get_andclauseargs(qual)) 
  517.         t_list = nappend1(t_list,qualcleanup(CAR(temp)));
  518.           new_and_args = remove_duplicates (t_list,equal);
  519.  
  520.           if(length (new_and_args) > 1) 
  521.         return (make_andclause (new_and_args));
  522.           else 
  523.            return (CAR (new_and_args));
  524.      }
  525.      else 
  526.        if (or_clause (qual)) {
  527.         LispValue temp = LispNil;
  528.         LispValue t_list = LispNil;
  529.         LispValue new_or_args = LispNil;
  530.  
  531.         foreach (temp,get_orclauseargs(qual)) 
  532.           t_list = nappend1(t_list,qualcleanup(CAR(temp)));
  533.         new_or_args = remove_duplicates (t_list,equal);
  534.  
  535.         if(length (new_or_args) > 1) 
  536.           return (make_orclause (new_or_args));
  537.         else 
  538.           return (CAR (new_or_args));
  539.        } else 
  540.           if (not_clause (qual)) 
  541.            return (make_notclause (qualcleanup 
  542.                     (get_notclausearg (qual))));
  543.           else 
  544.         return (qual);
  545. }  /* function end   */
  546.  
  547. /*    
  548.  *        remove-ands
  549.  *    
  550.  *        Remove the explicit "AND"s from the qualification:
  551.  *            ("AND" A B) => (A B)
  552.  *    
  553.  *    RETURNS : qual
  554.  *        MODIFIES: qual
  555.  */
  556.  
  557. /*  .. cnfify, remove-ands     */
  558.  
  559. LispValue
  560. remove_ands (qual)
  561.      LispValue qual ;
  562. {
  563.      LispValue t_list = LispNil;
  564.  
  565.      if(null (qual)) 
  566.        return (LispNil);
  567.      if (is_clause (qual)) 
  568.        return (make_clause (get_op (qual),
  569.            lispCons(remove_ands ((LispValue)get_leftop (qual)),
  570.                lispCons(remove_ands((LispValue)get_rightop(qual)),
  571.                 LispNil))));
  572.      if (and_clause (qual)) {
  573.      LispValue temp = LispNil;
  574.      foreach (temp,get_andclauseargs(qual))
  575.         t_list = nappend1(t_list,remove_ands(CAR(temp)));
  576.      return(t_list);
  577.      } else 
  578.        if (or_clause (qual)) {
  579.        LispValue temp = LispNil;
  580.        foreach (temp,get_orclauseargs(qual))
  581.           t_list = nappend1(t_list,remove_ands(CAR(temp)));
  582.        return (make_orclause (t_list));
  583.        } else 
  584.      if (not_clause (qual)) 
  585.        return (make_notclause (remove_ands 
  586.                     (get_notclausearg (qual))));
  587.      else 
  588.        return (qual);
  589.  }  /* function end   */
  590.  
  591. /*         ==========================
  592.  *         EXISTENTIAL QUALIFICATIONS
  593.  *         ==========================
  594.  */
  595.  
  596. /*    
  597.  *        update-relations
  598.  *    
  599.  *        Returns the range table indices (i.e., varnos) for all relations which
  600.  *        are referenced in the target list.
  601.  *    
  602.  */
  603.  
  604. /*  .. preprocess-qualification     */
  605.  
  606. LispValue
  607. update_relations (tlist)
  608.      LispValue tlist ;
  609. {
  610.      LispValue xtl = LispNil;
  611.      LispValue var = LispNil;
  612.      LispValue t_list1 = LispNil;    /* used in mapcan  */
  613.      LispValue t_list2 = LispNil;
  614.  
  615.      /* was mapCAR nested with mapcan  
  616.      foreach(xtll,tlist) 
  617.        t_list1 = nconc (t_list1,pull_var_clause(get_expr(CAR(xtl))));
  618.      foreach(var,t_list1) 
  619.        t_list2 = nappend1(t_list2,get_varno(CAR(var)));
  620.      return(remove_duplicates (t_list2));
  621.  
  622.      XXX - fix me after "retrieve x=1" works
  623.      by uncommenting the code above and removing the return below
  624.  
  625.      */
  626.      return(LispNil);
  627. } /* function end  */
  628.  
  629. /*    
  630.  *        update-clauses
  631.  *    
  632.  *        Returns those qualifier clauses which reference ONLY non-update
  633.  *        relations, i.e., those that are not referenced in the targetlist
  634.  *    
  635.  *        A var node is existential iff its varno
  636.  *        (1) does not reference a relation which is referenced
  637.  *            in the target list, and
  638.  *        (2) is a number (non-numbers are references to internal 
  639.  *            results, etc., which are non-existential).
  640.  *    
  641.  *        Note that clauses without any vars are considered to
  642.  *        be existential.
  643.  *    
  644.  */
  645. LispValue
  646. update_clauses (update_relids,qual,command)
  647.      LispValue update_relids,qual,command ;
  648. {
  649.      return (LispNil);
  650. }
  651.  
  652. /*   XXX Close but no cigar.  Turn it off for now.
  653.  *  .. preprocess-qualification
  654.  *  (defun update-clauses (update-relids qual command)
  655.  *    #+opus43 (declare (special update-relids))
  656.  *    (case command
  657.  *      (delete
  658.  *       (collect #'(lambda (clause)
  659.  *                #+opus43 (declare (special update-relids))
  660.  *                (every #'(lambda (var)
  661.  *                   #+opus43 (declare (special update-relids))
  662.  *                   (and (var-p var)
  663.  *                        (integerp (get_varno var))
  664.  *                        (not (member (get_varno var)
  665.  *                             update-relids))))
  666.  *                   (pull_var_clause clause)))
  667.  *            qual))))
  668.  */
  669.